package HASH;

import java.util.*;

public class item49 {
    public static List<List<String>> groupAnagrams(String[] strs) {
        //思路1.得到一个字符串，先把他的所有排列组合都得到一遍再与目标的list数组取交集,是错的
        //
        //思路2.把字符串转化为字符数组，对字符数组排序再转化为字符串为键，字母异位的为值

//
//        List<Character> track = new LinkedList<>();
//        List<String> union = Arrays.asList(strs);
//        List<List<String>> res = new LinkedList<>();
//        List<String> union1 = new LinkedList<>(union);
//        int frquent = 0;
//        if(union1.contains(""))
//        {
//            frquent = Collections.frequency(union1,"");
//            List <String>  group = new LinkedList<>();
//            for (int i = 0; i < frquent; i++) {
//                group.add("");
//            }
//            union1.removeAll(group);
//            res.add(group);
//        }
//        strs = union1.toArray(new String[union1.size()]);
//       while (strs.length!=0)
//       {
//           List <String>  group = new LinkedList<>();
//           String str = strs[0];
//           char [] c = str.toCharArray();
//           reBack( group, track,c);
//           group.retainAll(union1);
//
//           union1.removeAll(group);
//           strs = union1.toArray(new String[union1.size()]);
//
////            在这里需要把已经加入list的字符串去掉
//           res.add(group);
//       }
////        List<String> ls = new ArrayList();
////        for (int i = 0; i <frquent-1; i++) {
////
////            ls.add("");
////            res.add(ls);
////        }
//
//        return res;

        if(strs.length==0)
        {
            return new ArrayList<>();
        }
        HashMap<String,List> map = new HashMap<>();
        for(String str :strs)
        {
            char[] c= str.toCharArray();
            Arrays.sort(c);
            String key = String.valueOf(c);
            if(!map.containsKey(key))
            {
                map.put(key,new ArrayList());
            }
            map.get(key).add(str);
        }
        System.out.println(map.values());
        List res =new ArrayList<>(map.values());
        return  res;
    }
    public static void reBack(List<String> group,List<Character> track,char [] c)
    {


        if(track.size() ==c.length)
        {
            StringBuffer buffer = new StringBuffer();
            for (int i = 0; i < track.size(); i++) {
                buffer.append(track.get(i));
            }
            String s = buffer.toString();
            group.add(s);
            return;
        }
        for (int i = 0; i <c.length ; i++) {
            if(track.contains(c[i]))
            {
                continue;
            }
            track.add(c[i]);
            reBack(group,track,c);
            //如何移除最后一个下标呢
            track.remove(track.size()-1);

        }

    }

    public static void main(String[] args) {
      String[]  strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
    List<List<String>> res = groupAnagrams(strs);
        System.out.println(res);


    }
}
